Is MiniZinc 'stochastic'?
29 views
Skip to first unread message
Andrew Gill
Mar 14, 2025, 12:24:41 PMMar 14
to MiniZinc
Hi - If I print out intermediate solutions for a "solve minimize" and run MiniZinc twice, I seem to get different solution paths. So is it 'stochastic' in some sense, and in what sense?
Is there something like a 'seed' that can be used to ensure 'repeatability'?
And if I have p processors, instead of using them all in parallel (with -p) under one run, is there any sense (if it were programmatically possible) in trying p (non-parallel) runs and dynamically inserting upper-bounds on the objective across the runs??
I hope that all makes sense!
Thanks
Andrew
Mikael Zayenz Lagerkvist
Mar 16, 2025, 12:34:01 PMMar 16
to mini...@googlegroups.com
Hi,
MiniZinc in itself is not stochastic, but the underlying solver used
may very well be, especially if multiple threads are used. In general,
it is quite hard to write combinatorial optimization solvers that are
deterministic if you combine it with threads. This is an unfortunate
fact when using systems like this, and something one has to work with
when using them.
> Is there something like a 'seed' that can be used to ensure 'repeatability'?
If you use a deterministic solver with a deterministic search strategy
and a single thread, then you will get repeatability but also most
likely a lot longer run-times. For example, Gecode with one thread and
a specified search strategy and no restarts should in most cases be
deterministic.
> And if I have p processors, instead of using them all in parallel (with -p) under one run,
> is there any sense (if it were programmatically possible) in trying p (non-parallel) runs
> and dynamically inserting upper-bounds on the objective across the runs??
This is how many solvers work internally (for example, OR-Tools which
has a large set of different strategies used for different threads),
and re-implementing it externally would not give you anything really.
If your goal is to always get the same optimal solution among a set of
equally good optimal solutions, then it might be better to consider a
two-stage approach. First find some optimal solution. Then fix the
objective value, and re-run a search that instead optimizes for how it
looks (for example, the lexicographically smallest such solution).
Might take a lot longer, but it will give you predictability for the
end result.
Cheers,
Mikael
> --
> You received this message because you are subscribed to the Google Groups "MiniZinc" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/minizinc/fd57a6ab-bb5d-4706-87ac-a0e533652d5an%40googlegroups.com.
--
Mikael Zayenz Lagerkvist
MiniZinc in itself is not stochastic, but the underlying solver used
may very well be, especially if multiple threads are used. In general,
it is quite hard to write combinatorial optimization solvers that are
deterministic if you combine it with threads. This is an unfortunate
fact when using systems like this, and something one has to work with
when using them.
> Is there something like a 'seed' that can be used to ensure 'repeatability'?
and a single thread, then you will get repeatability but also most
likely a lot longer run-times. For example, Gecode with one thread and
a specified search strategy and no restarts should in most cases be
deterministic.
> And if I have p processors, instead of using them all in parallel (with -p) under one run,
> is there any sense (if it were programmatically possible) in trying p (non-parallel) runs
> and dynamically inserting upper-bounds on the objective across the runs??
has a large set of different strategies used for different threads),
and re-implementing it externally would not give you anything really.
If your goal is to always get the same optimal solution among a set of
equally good optimal solutions, then it might be better to consider a
two-stage approach. First find some optimal solution. Then fix the
objective value, and re-run a search that instead optimizes for how it
looks (for example, the lexicographically smallest such solution).
Might take a lot longer, but it will give you predictability for the
end result.
Cheers,
Mikael
> You received this message because you are subscribed to the Google Groups "MiniZinc" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/minizinc/fd57a6ab-bb5d-4706-87ac-a0e533652d5an%40googlegroups.com.
--
Mikael Zayenz Lagerkvist
Reply all
Reply to author
Forward
0 new messages
Search
Clear search
Close search
Google apps
Main menu